/***尚硅谷Java数据结构与java算法                   ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***单向链表，考虑使用编号排序      P19-23            ***/
/***C++ 实现版本    written by Daniel           ***/
#include <string>
#include <sstream>
#include <iostream>
#include <stack>
// #include <memory>
// using std::shared_ptr;
using std::string;
using std::cout;
using std::endl;
using std::stack;
class HeroNode
{
public:
    HeroNode(int hNum, string hName, string hNickName)
    {
        this->num = hNum;
        this->name = hName;
        this->nickName = hNickName;
    }
    HeroNode():num(0),name(""),nickName("")
    {
    }
    string toString()
    {
        return "Hero [No=" + std::to_string(num) + "\t" + "name=" + name + +"\t"
                                                                            "nickname=" +
               nickName + "]";
    }
    int num;
    string name;
    string nickName;
    HeroNode *next = nullptr;
private:
};

class HeroNodeLinkedList
{
public:
    void addNodeByOrder(HeroNode *heroNode)
    {
        HeroNode *temp;
        temp = head;
        //找到插入的位置   temp.num<=heroNode.num && temp.next.num>=heroNode.num
        while (temp->next != nullptr)
        {
            if (temp->num <= heroNode->num && temp->next->num > heroNode->num)
                break;
            temp = temp->next;
        }
        heroNode->next = temp->next;
        temp->next = heroNode;
    }
    HeroNode *findNode(int num)
    {
        bool flag = false;
        HeroNode *temp = head;
        while (1)
        {
            if (temp->next == nullptr)
            {
                break;
            }
            if (temp->num == num)
            {
                flag = true;
                return temp;
            }
        }
        if (flag == false)
        {
            return nullptr;
        }
    }
    void delNode(int num)
    {
        int flag = false;
        HeroNode *temp = head;
        while (1)
        {//最后一个节点会退出
            if (temp->next == nullptr)
            {
                break;
            }//说明找到了要删除的节点
            if (temp->next->num == num)
            {
                flag=true;
                HeroNode *nodeToDel = temp->next;
                temp->next = temp->next->next;
                if (nodeToDel != nullptr)
                {
                    delete nodeToDel;
                    nodeToDel = nullptr;
                }
                break;
            }
            temp = temp->next;
        }
        if (flag==true){
            std::cout<<"节点删除成功！"<<std::endl;
        }
        else{
            std::cout<<"节点删除失败！"<<std::endl;
        }
    }
    void Print()
    {
        HeroNode *temp;
        temp = this->head;
        while (temp != nullptr)
        {
            std::cout << temp->toString() << std::endl;
            temp = temp->next;
        }
        return;
    }
    static int getLength(HeroNode* head)
    {
        if (head==nullptr){
            return 0;
        }
        int length=0;
        HeroNode* temp=head;
        while (temp->next!=nullptr)
        {
            length++;
            temp=temp->next;
        }
        return length;        
    }
    //查找倒数第n个元素
    static HeroNode* findLastIndex(HeroNode* head, int index)
    {
        if (head==nullptr){
            return nullptr;
        }
        int length=getLength(head);
        if (index<=0||(index>length)){
            return nullptr;
        }
        HeroNode* temp=head;
        int size=length-index+1;
        for(;size>0;size--){
            temp=temp->next;
        }                   
        return temp;     
    }

    HeroNode* getHead()
    {
        return this->head;
    }
    //翻转链表
    void reserveList()
    {
        if (head->next==nullptr||head==nullptr){
            return;
        }
        auto reverseHead=new HeroNode();
        auto temp=head->next;
        while(temp!=nullptr)
        {
            HeroNode* curNode=temp;
            temp=temp->next;
            curNode->next=reverseHead->next;
            reverseHead->next=curNode;
        }        
        head->next=reverseHead->next;
        if (reverseHead!=nullptr){
            delete reverseHead;
            reverseHead=nullptr;
        }
    }
    //逆序打印链表，碰到逆序 考虑使用 栈 这种数据结构
    void reversePrint()
    {
        if (head==nullptr){
            cout<<"空链表，无法打印！\n";
        }
        auto temp=head->next;
        stack<HeroNode*> heroNodeStack;
        while (temp!=nullptr)
        {   
            heroNodeStack.push(temp);
            temp=temp->next;
        }
        while (heroNodeStack.size()!=0)
        {
            cout<<(heroNodeStack.top())->toString()<<endl;
            heroNodeStack.pop();
        }
        return;        
    }

    //析构函数
    ~HeroNodeLinkedList()
    {
        std::cout << "析构链表" << std::endl;
        HeroNode *temp = this->head;
        HeroNode *tempToFree;
        while (temp->next != nullptr)
        {
            tempToFree = temp;
            temp = temp->next;
            delete tempToFree;
            if (tempToFree != nullptr)
                tempToFree = nullptr;
        }
        delete temp;
        if (temp != nullptr)
            temp = nullptr;
        if (temp == nullptr)
        {
            std::cout << "析构成功" << std::endl;
        }
    }

private:
    HeroNode *head = new HeroNode(0, "", "");
};

int main(int argc, char **argv)
{
    HeroNode *hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode *hero2 = new HeroNode(2, "吴用", "智多星");
    HeroNode *hero3 = new HeroNode(4, "林冲", "豹子头");
    HeroNode *hero4 = new HeroNode(3, "鲁智深", "花和尚");
    HeroNode *hero5 = new HeroNode(6, "柴进", "小旋风");
    HeroNode *hero6 = new HeroNode(7, "张进", "浪里白条");
    HeroNode *hero7 = new HeroNode(3, "武松", "行者");

    HeroNodeLinkedList *heroList = new HeroNodeLinkedList();
    heroList->addNodeByOrder(hero1);
    heroList->addNodeByOrder(hero2);
    heroList->addNodeByOrder(hero3);
    heroList->addNodeByOrder(hero4);
    heroList->addNodeByOrder(hero5);
    heroList->addNodeByOrder(hero6);
    heroList->addNodeByOrder(hero7);
    cout<<HeroNodeLinkedList::getLength(heroList->getHead())<<endl;
    heroList->Print();
    heroList->delNode(4);
    heroList->delNode(7);
    heroList->delNode(5);
    heroList->Print();
    cout<<HeroNodeLinkedList::getLength(heroList->getHead())<<endl;
    cout<<HeroNodeLinkedList::findLastIndex(heroList->getHead(),1)->toString()<<endl;
    cout<<HeroNodeLinkedList::findLastIndex(heroList->getHead(),2)->toString()<<endl;
    heroList->reserveList();
    cout<<"after reverse the list!"<<endl;
    heroList->Print();
    cout<<"reverse print the list"<<endl;
    heroList->reversePrint();
    if (heroList != nullptr)
    {
        delete heroList;
        heroList = nullptr;
    }
    return 0;
}